(0) Obligation:
Runtime Complexity TRS:
The TRS R consists of the following rules:
and(false, false) → false
and(true, false) → false
and(false, true) → false
and(true, true) → true
eq(nil, nil) → true
eq(cons(T, L), nil) → false
eq(nil, cons(T, L)) → false
eq(cons(T, L), cons(Tp, Lp)) → and(eq(T, Tp), eq(L, Lp))
eq(var(L), var(Lp)) → eq(L, Lp)
eq(var(L), apply(T, S)) → false
eq(var(L), lambda(X, T)) → false
eq(apply(T, S), var(L)) → false
eq(apply(T, S), apply(Tp, Sp)) → and(eq(T, Tp), eq(S, Sp))
eq(apply(T, S), lambda(X, Tp)) → false
eq(lambda(X, T), var(L)) → false
eq(lambda(X, T), apply(Tp, Sp)) → false
eq(lambda(X, T), lambda(Xp, Tp)) → and(eq(T, Tp), eq(X, Xp))
if(true, var(K), var(L)) → var(K)
if(false, var(K), var(L)) → var(L)
ren(var(L), var(K), var(Lp)) → if(eq(L, Lp), var(K), var(Lp))
ren(X, Y, apply(T, S)) → apply(ren(X, Y, T), ren(X, Y, S))
ren(X, Y, lambda(Z, T)) → lambda(var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), ren(X, Y, ren(Z, var(cons(X, cons(Y, cons(lambda(Z, T), nil)))), T)))
Rewrite Strategy: FULL
(1) DecreasingLoopProof (EQUIVALENT transformation)
The following loop(s) give(s) rise to the lower bound Ω(2n):
The rewrite sequence
ren(X, Y, apply(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), S)) →+ apply(lambda(var(cons(X, cons(Y, cons(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), nil)))), lambda(var(cons(X, cons(Y, cons(lambda(var(cons(Z35986_0, cons(var(cons(X, cons(Y, cons(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), nil)))), cons(lambda(Z37470_0, T37471_0), nil)))), ren(Z35986_0, var(cons(X, cons(Y, cons(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), nil)))), ren(Z37470_0, var(cons(Z35986_0, cons(var(cons(X, cons(Y, cons(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), nil)))), cons(lambda(Z37470_0, T37471_0), nil)))), T37471_0))), nil)))), ren(X, Y, ren(var(cons(Z35986_0, cons(var(cons(X, cons(Y, cons(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), nil)))), cons(lambda(Z37470_0, T37471_0), nil)))), var(cons(X, cons(Y, cons(lambda(var(cons(Z35986_0, cons(var(cons(X, cons(Y, cons(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), nil)))), cons(lambda(Z37470_0, T37471_0), nil)))), ren(Z35986_0, var(cons(X, cons(Y, cons(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), nil)))), ren(Z37470_0, var(cons(Z35986_0, cons(var(cons(X, cons(Y, cons(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), nil)))), cons(lambda(Z37470_0, T37471_0), nil)))), T37471_0))), nil)))), ren(Z35986_0, var(cons(X, cons(Y, cons(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), nil)))), ren(Z37470_0, var(cons(Z35986_0, cons(var(cons(X, cons(Y, cons(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), nil)))), cons(lambda(Z37470_0, T37471_0), nil)))), T37471_0)))))), ren(X, Y, S))
gives rise to a decreasing loop by considering the right hand sides subterm at position [0,1,0,0,1,1,0,1,2].
The pumping substitution is [T37471_0 / apply(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), S)].
The result substitution is [X / Z37470_0, Y / var(cons(Z35986_0, cons(var(cons(X, cons(Y, cons(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), nil)))), cons(lambda(Z37470_0, T37471_0), nil))))].
The rewrite sequence
ren(X, Y, apply(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), S)) →+ apply(lambda(var(cons(X, cons(Y, cons(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), nil)))), lambda(var(cons(X, cons(Y, cons(lambda(var(cons(Z35986_0, cons(var(cons(X, cons(Y, cons(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), nil)))), cons(lambda(Z37470_0, T37471_0), nil)))), ren(Z35986_0, var(cons(X, cons(Y, cons(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), nil)))), ren(Z37470_0, var(cons(Z35986_0, cons(var(cons(X, cons(Y, cons(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), nil)))), cons(lambda(Z37470_0, T37471_0), nil)))), T37471_0))), nil)))), ren(X, Y, ren(var(cons(Z35986_0, cons(var(cons(X, cons(Y, cons(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), nil)))), cons(lambda(Z37470_0, T37471_0), nil)))), var(cons(X, cons(Y, cons(lambda(var(cons(Z35986_0, cons(var(cons(X, cons(Y, cons(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), nil)))), cons(lambda(Z37470_0, T37471_0), nil)))), ren(Z35986_0, var(cons(X, cons(Y, cons(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), nil)))), ren(Z37470_0, var(cons(Z35986_0, cons(var(cons(X, cons(Y, cons(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), nil)))), cons(lambda(Z37470_0, T37471_0), nil)))), T37471_0))), nil)))), ren(Z35986_0, var(cons(X, cons(Y, cons(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), nil)))), ren(Z37470_0, var(cons(Z35986_0, cons(var(cons(X, cons(Y, cons(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), nil)))), cons(lambda(Z37470_0, T37471_0), nil)))), T37471_0)))))), ren(X, Y, S))
gives rise to a decreasing loop by considering the right hand sides subterm at position [0,1,1,2,1,0,1,1,0,1,2].
The pumping substitution is [T37471_0 / apply(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), S)].
The result substitution is [X / Z37470_0, Y / var(cons(Z35986_0, cons(var(cons(X, cons(Y, cons(lambda(Z35986_0, lambda(Z37470_0, T37471_0)), nil)))), cons(lambda(Z37470_0, T37471_0), nil))))].
(2) BOUNDS(2^n, INF)